package com.lijing.binarySortTree;

/**
 * @Description TODO
 * @title: BinarySortTree
 * @Author LiJing
 * @Date: 2021/3/2910:31 上午
 * @Version 1.0
 */
public class BinarySortTree {
    private Node root;

    public BinarySortTree(Node root) {
        this.root = root;
    }

    public BinarySortTree() {
    }

    /**
     * 添加节点
     * @param node 待添加的节点
     */
    public void add(Node node){
        if (this.root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (root == null) {
            System.out.println("二叉排序树为空，无法遍历！");
        }else {
            root.infixOrder();
        }
    }

    /**
     * 查找节点
     * @param value 待查找的节点value
     * @return 返回待查找的节点
     */
    public Node search(int value){
        if (root == null){
            return null;
        }else {
            return root.search(value);
        }
    }

    /**
     * 查找节点的父节点
     * @param value 待查找的节点value
     * @return 返回待查找的节点的父节点
     */
    public Node searchParent(int value){
        if (root == null) {
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    /**
     * 删除节点
     * @param value 待删除的节点的value
     */
    public void deleteNode(int value){
        if (root == null){
            return;
        }else {
            /*
             * @Date: 2021/3/29 11:51 上午
             * Step 1: 查找到要删除的节点targetNode
             */
            Node targetNode = search(value);
            if (targetNode == null){
                return;
            }
            /*
             * 如果带删除的节点就是根节点，且根节点再无子节点
             */
            if (root.getLeft() == null && root.getRight() == null){
                root =null;
            }
            /*
             * @Date: 2021/3/29 11:55 上午
             * Step 2: 查找targetNode的父节点
             */
            Node parent = searchParent(value);

            /*分情况讨论
             * ①待删除的节点是叶子节点，找到父节点，接删除节点直接删除
             * ②待删除节点只有一个子节点，将待删除节点的子节点挂载到待删除节点的父节点上
             * ③待删除节点有两个子节点，向右子节点寻找一个value最小的节点，使用temp暂时保存其值，
             * 然后将其删除，并将待删除节点的value值改为temp
             */

            /*
             * ①删除叶子节点
             */
            if (targetNode.getLeft() == null && targetNode.getRight() ==null){
                if (parent.getLeft() != null && parent.getLeft().getValue() == targetNode.getValue()){
                    parent.setLeft(null);
                }else if (parent.getRight() != null && parent.getRight().getValue() == targetNode.getValue()){
                    parent.setRight(null);
                }
            }
            /*
             * ②待删除节点只有一个右子节点
             */
            else if (targetNode.getLeft() == null && targetNode.getRight() != null){
                if (parent != null){
                    if (parent.getLeft().getValue() == targetNode.getValue()){
                        parent.setLeft(targetNode.getRight());
                    }else {
                        parent.setRight(targetNode.getRight());
                    }
                }else {
                    root = targetNode.getRight();
                }

            }
            /*
             * ②待删除节点只有一个左子节点
             */
            else if (targetNode.getRight() == null && targetNode.getLeft() != null){
                if (parent != null) {
                    if (parent.getLeft().getValue() == targetNode.getValue()){
                        parent.setLeft(targetNode.getLeft());
                    }else {
                        parent.setRight(targetNode.getLeft());
                    }
                }else {
                    root = targetNode.getLeft();
                }
            }
            /*
             * ③待删除节点既有左子节点又有右子节点
             */
            else {
                Node tempNode = targetNode.getRight().getMinNode();
                deleteNode(tempNode.getValue());
                targetNode.setValue(tempNode.getValue());
            }


        }
    }

}
